package com.tlvip.arithmetic.ch06;

/**
 * <p>description：递归实现</p>
 * <p>copyright： copyright(C)2016-2099</p>
 * <p>Life is short,we need passion</p>
 * <p>Summary： </p>
 * <p>instructions： </p>
 * Date 1/25/21</p>
 * Author mac
 *
 * @version 1.0
 */
public class RecursionTest {


    /**
     * 非递归完成斐波拉契数列
     * 优化思路：使用循环代替递归
     *
     * @param n
     * @return
     */
    public static int getNoFab(int n) {
        if (n <= 2) {
            return 1;
        }
        int fabNum = 0;
        int a = 1;
        int b = 1;
        for (int i = 3; i <= n; i++) {
            fabNum = a + b;
            a = b;
            b = fabNum;
        }
        return fabNum;
    }


    public static int getNoFab2(int n) {
        int num = 0;
        if (n <= 2) {
            return 1;
        } else {
            int data[] = new int[n];
            for (int i = 0; i < n; i++) {
                if (i < 2) {
                    data[i] = 1;
                } else {
                    data[i] = data[i - 1] + data[i - 2];
                }
            }
            num = data[n - 1];
        }
        return num;
    }

    /**
     * 求阶乘-优化前的算法
     *
     * @param n
     * @return
     */
    public static int getFac(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * getFac(n - 1);
    }

    /**
     * 尾递归-求阶乘-优化后的算法
     *
     * @param n
     * @return
     */
    public static int tailFac(int n, int res) {
        System.out.println(n + ":" + res);
        if (n <= 1) {
            return 1;
        }
        return tailFac(n - 1, n * res);
    }


    /**
     * 求斐波拉契数列
     * 时间复杂度O(2^n)，空间复杂度2^n
     * 每增加一个点，都要引出两个分支
     *
     * @param n
     * @return
     */
    public static int getFab(int n) {
        if (n <= 2) {
            return 1;
        }
        return getFab(n - 1) + getFab(n - 2);
    }

    /**
     * 尾递归-计算斐波拉契数列
     * 思想：将结果保存起来，参照倒序来做，不用回溯
     * @param pre 上上次结果
     * @param res 上次结果
     * @param n
     * @return
     */
    public static int getFabTail(int pre, int res, int n) {
        if (n <= 2) {
            return res;
        }
        // 将res转换成上上次结果
        // 将pre + res转换成上次结果
        return getFabTail(res, pre + res, n - 1);
    }


    public static void main(String[] args) {
//        for (int i = 1; i <= 45; i++) {
//            long start = System.currentTimeMillis();
//            System.out.println(i + ":" + getFab(i) + "耗费" + (System.currentTimeMillis() - start) + "ms");
//        }
//        System.out.println("=====================");
//        for (int i = 1; i <= 45; i++) {
//            long start = System.currentTimeMillis();
//            System.out.println(i + ":" + getNoFab(i) + "耗费" + (System.currentTimeMillis() - start) + "ms");
//        }
//
//        System.out.println("=====================");
//        for (int i = 1; i <= 45; i++) {
//            long start = System.currentTimeMillis();
//            System.out.println(i + ":" + getNoFab2(i) + "耗费" + (System.currentTimeMillis() - start) + "ms");
//        }
//        System.out.println("=====================");
//        tailFac(5, 1);

//        for (int i = 1; i <= 45; i++) {
//            long start = System.currentTimeMillis();
//            System.out.println(i + "-" + getFabTail(1, 1, i) + "耗费:" + (System.currentTimeMillis() - start));
//        }
        System.out.println(getFabTail(5, 9, 5));
    }
}
